package hot100.logos81To90;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author logos
 * date 2025/7/18 11:38
 * @version v1.0
 * @Package hot100.logos81To90
 */
public class logos86 {

    /**
     * 86. 单词拆分
     * https://leetcode.cn/problems/word-break/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            int maxLen = 0;
            for (String word : wordDict) {
                maxLen = Math.max(maxLen, word.length());
            }
            Set<String> words = new HashSet<>(wordDict);
            int n = s.length();
            boolean[] dp = new boolean[n + 1];
            dp[0] = true;
            for (int i = 0; i <= n; i++) {
                for (int j = i - 1; j >= Math.max(i - maxLen, 0); j--) {
                    if (dp[j] && words.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
            return dp[n];
        }
    }
}
